PUBLIC MARKS from solveig_vidal with tag "chaînes de caractères"

Dans le domaine du traitement automatique des langues naturelles, le traitement des erreurs représente un sous-domaine à lui seul. Paradoxalement, il trouve en partie son origine dans le traitement des langages artificiels ; les premiers systèmes de correction d'erreurs ont été en effet élaborés dans le but de corriger les erreurs que commettaient les programmeurs lors de la rédaction de programmes informatiques.

Le site de François Parmentier (voir dans mes amis) explique la notion de recherche de chaîne approximative avec calcul de similarité et de distance d'édition. Son exemple est très didactique, c'est la recherche de chaîne approximative pour les nuls. ------------------ François Parmentier's website where approximative string matching is well explained with useful example.

Technologies de l'information -- Classement international et comparaison de chaînes de caractères -- Méthode de comparaison de chaînes de caractères et description du modèle commun et adaptable d'ordre de classement

EXACT STRING MATCHING ALGORITHMS

Crochemore et Perrin ont propose un algorithme de recherche de motifs elegant lineaire en temps, utilisant une memoire constante. Le nombre de comparaisons de symboles est majore par 2n - m. Ce papier montre comment modifier leur algorithme pour executer moins de comparaisons. Pour chaque [??] fixe, ce nouvel algorithme est lineaire en temps, utilise un espace constant et fait au plus [??] comparaisons. Avec un espace 0(log m), au plus [??] comparaisons sont necessaires. L'etape de preprocessing prend aussi un temps lineaire avec un espace constant. Ce sont les premiers algorithmes de recherche de motifs qui font moins de 2n - m comparaisons en utilisant un espace sous-lineaire.